\section{Charging scheme} \label{sec:charging_scheme}
The general charging scheme is described in
Algorithm~\ref{alg:charging_scheme}.
%
\begin{algorithm}[t]
\caption{\sc Charging Scheme}\label{alg:charging_scheme}
\begin{algorithmic}[1]
\small \STATE For all $t$ and $e\in E(G)$, $v\in V(G)$, set
$ch_t(e):=0$ and $ch_t(v):=0$. \label{line:begin_init}

\FOR{any edge $e_t\in OPT$ that arrives at time $t$}

\STATE Let $e=uv$ be the edge in $M_t$ that prevents $e_t$.

\STATE Let $t'=\text{appearance-time}(e, t)$\\ (Define
appearance-time$(e, t)$ to be $t'$ such that $e\notin M_{t'-1}$ and
$e\in M_{t''}$ for all $t'\leq t''\leq t$.)

\STATE Set $ch_{t'}(v):=w(e_t)$ for $v\in e\cap e_t$. (Note that
$|e\cap e_t|=1$ by lemma~\ref{lem:opt_has_degree_one}.)

\ENDFOR \label{line:end_init}

\STATE

\FOR{$\tau=1..m-1$} \label{line:begin_clearing}


\STATE \textbf{for} any $uv\in M_\tau\cap M_{\tau+1}$ \textbf{do}
$ch_{\tau+1}(uv):=ch_{\tau+1}(uv)+ch_\tau(uv)$,
$ch_{\tau+1}(u):=ch_{\tau+1}(u)+ch_\tau(u)$ and
$ch_{\tau+1}(v):=ch_{\tau+1}(v)+ch_\tau(v)$ \textbf{end for}

\FOR{$uv\in M_{\tau}\setminus M_{\tau+1}$}

\STATE \label{line:moving_charge} {\sc Move-Charge}($uv$, $\tau$)

\COMMENT{Make $ch_{\tau}(uv)=ch_\tau(u)=ch_\tau(v)=0$ by moving some
charge to $l_\tau(uv)$ and the rest to $ch_{\tau'}(u)$,
$ch_{\tau'}(v)$, $ch_{\tau'}(u')$, $ch_{\tau'}(v')$,
$ch_{\tau'}(u'u)$, and $ch_{\tau'}(v'v)$ for some $\tau'>\tau$, $u'$
and $v'$. (see details in text) }

\ENDFOR

\STATE (The Invariant can be checked at this point.)
\label{line:invariant}

\ENDFOR \label{line:end_clearing}
\end{algorithmic}
\end{algorithm}
%
The idea is to keep charge on edges in $M_t$ and their end vertices,
for all $t$. In line \ref{line:begin_init} to \ref{line:end_init} of
Algorithm~\ref{alg:charging_scheme}, we charge an optimal edge to
the end vertex of and edge that prevents it.

Note that, for the latter use, we charge an edge $e$ at its
appearance time. The function appearance-time$(e, t)$ can be thought
of as the time $e$ starts continuously appearing in the matching
until time $t$. It is straightforward that
Invariant~\ref{inv:main}(\ref{inv:charge_more_than_opt}) is
satisfied after line~\ref{line:end_init} is finished.

From line \ref{line:begin_clearing} to line \ref{line:end_clearing}
we keep moving charge that is put on variables associated with time
$\tau$ to $l_\tau$ and variables associated with time $\tau'>\tau$.
We do this using {\sc Move-Charge} algorithm (\cf\
Algorithm~\ref{alg:move_charge}). This algorithm mainly clear charge
on $ch_\tau(u)$, $ch_\tau(v)$, and $ch_\tau(uv)$ and add new charge
on other variables depending on which case is satisfied. It does
this in such a way that the total new charge is at least $ch_\tau(u)
+ ch_\tau(v) + ch_\tau(uv)$ so that it satisfies
Invariant~\ref{inv:main}(\ref{inv:charge_more_than_opt}). We give
more details of how it satisfies the Invariant in the next section.

Note that the invariant can be checked every time we finish the for
loop (i.e., line~\ref{line:invariant}) of the {\sc Charging Scheme}.
Most cases in Algorithm~\ref{alg:move_charge} are straightforward
except Case~3.2.1. We explain this case here. First, we explain the
construction of {\it charging chain} as follows.

\begin{definition}[Charging Chain Construction.] \label{def:charging_chain}
Consider any time $\tau'$ where
$e_{\tau'}\in OPT$. We construct a {\it charging chain} at time
$\tau'$ as follows. First, let $v_0v'_0=e_{\tau'}$ be in the chain.
Now we extend the chain from $v_0$. Add $v_0u_1$ to the chain where
$v_0u_1$ is the edge in $M_{\tau'}$ covering $v_0$. (If $v_0u_1$
does not exist, we stop extending the chain from $v_0$.) Then, let
$u_1v_1$ = shadow($v_0u_1$, $u_1$). Add $u_1v_1$ to the chain if
$ch_{\tau''}(u_1)=0$ and $ch_{\tau''}(v_1)>0$ where $\tau''$ be the
time that $u_1v_1$ is
%
%\begin{algorithm}[H]
%\caption{{\sc Move-Charge} ($e=uv$, $\tau$)} \label{alg:move_charge}%
%%\begin{figure}
%%\begin{tabular}{|r|}
%%Use the first case that applies.
%\begin{description}
%  \item[Initial] Let
%    $e^1=uu'$ and $e^2=vv'$ be edges in $M_{\tau+1}$. If $e^1$ does not
%    exists, let $ch_{\tau}(u)=ch_{\tau+1}(u)=0$ and $f_t(u)=0$. Do the
%    same thing if $e^2$ does not exist.
%    (Note that one of $e^1$ and $e^2$ must exists and must be
%    $e_{\tau+1}$ as $e$ is in $M_\tau$ but not in $M_{\tau+1}$.)\\
%    For any variable $v$ and value $c$, define $v\oplus c$ by
%    $v:=v+c$ (i.e., increase $v$ by $c$).
%  \item[Case 1] When $ch_\tau(u)=ch_\tau(v)=0$ ($uv$ has no vertex
%  charge and has charge at most $\alpha w(uv)$ on edge.)
%    \begin{itemize}
%    \item $ch_{\tau+1}(e^1)\oplus\beta\gamma f_\tau(u)w(uv)$
%    \item $ch_{\tau+1}(e^2)\oplus\beta\gamma f_\tau(v)w(uv)$
%    \end{itemize}
%  %
%  \item[Case 2] When $ch_\tau(u)>0$ and $ch_\tau(v)>0$. ($uv$ has
%  positive charge at most $\delta w(uv)$ on both vertices and charge at
%  most $\beta$ on edge.)
%    \begin{itemize}
%    \item $ch_{\tau+1}(e^1)\oplus\beta\gamma f_\tau(u)w(uv)$
%    \item $ch_{\tau+1}(e^2)\oplus\beta\gamma f_\tau(v)w(uv)$
%    \item $ch_{\tau+1}(u)\oplus\gamma f_\tau(u)w(uv)$
%    \item $ch_{\tau+1}(v)\oplus\gamma f_\tau(v)w(uv)$
%    \end{itemize}
%  %
%  \item[Case 3] When $ch_\tau(u)>0$ and $ch_\tau(v)=0$. ($uv$ has
%  charge only on one vertex)
%  \begin{description}
%  \item[Case 3.1] When $ch_{\tau+1}(v)=0$ or
%  $ch_\tau(v')=ch_{\tau+1}(v')=0$. (When one of $v$, $v'$ will have no charge
%  at $\tau+1$. That is, $vv'$ can hold charge $\alpha$ on edge at time
%  $\tau+1$.
%    \begin{itemize}
%    \item $ch_{\tau+1}(e^1)\oplus\beta \gamma f_\tau(u)w(e)$
%    \item $ch_{\tau+1}(e^2)\oplus \alpha \gamma f_\tau(v)w(e)$
%    \item $ch_{\tau+1}(u)\oplus f_\tau(u)w(e)$
%    \end{itemize}
%  %
%  \item[Case 3.2] When $ch_{\tau+1}(v)>0$ and either $ch_\tau(v')>0$ or
%  $ch_{\tau+1}(v')>0$. (That is, when $vv'$ can hold charge $\beta$
%  on edge since it might receive some charge on both $v$ and $v'$.)
%    \begin{description}
%    \item[Case 3.2.1] For some $\tau'>\tau$ there is a charging chain at time $\tau'$
%    (\cf\ Definition~\ref{def:charging_chain}) containing $e_2$ and $e$.
%        \begin{itemize}
%        \item Let $u_{k+1}, v_k, u_k, ... , v_1, u_1, v_0, v'_0, u'_1, v'_1,
%         ..., u'_k, v'_k, u'_{k'+1}$, for some $k$ and $k'$  be
%        such charging chain where $v_0v'_0=e_{\tau'}$
%        and for all $1<i\leq k$, $u_iv_i$ = shadow-edge($v_{i-1}u_i, u_i$) and
%        $u'_iv'_i$ = shadow-edge($v'_{i-1}u'_i, u'_i$).
%%
%        \item For any $1\leq i\leq k$, let $v_iz_i$  be an edge that kills
%        $u_iv_i$. (That is, for $i$ such that $u_iv_i=e$,
%        $u_{i-1}v_i=e^2$ and $v_iz_i=e^1$.) Define $v'_iz'_i$
%        similarly.
%%
%        \item For all $1\leq i\leq k$, $ch_{\tau+1}(v_iz_i)\oplus \beta\gamma f_\tau(u_i)w(u_iv_i)$
%        \item For all $1\leq i\leq k$, $ch_{\tau+1}(v_{i-1}u_i)\oplus \beta\gamma f_\tau(v_i)w(u_iv_i)$
%        \item For all $0\leq i\leq k$, $ch_{\tau'}(v_i)=\gamma w(v_iu_{i+1})$
%        \item For all $1\leq i\leq k$,
%        $ch_{\tau}(u_iv_i)=ch_\tau(u_i)=ch_\tau(v_i)=0$.
%        \end{itemize}
%    %
%    %\textit{Note:} ***
%    %
%    \item[Case 3.2.2] For some $\tau'>\tau$ there is \textit{no} edge
%    $e_{\tau'}\in OPT$ covering $v'$
%        \begin{itemize}
%        \item $ch_{\tau+1}(e^1)\oplus\beta\gamma f_\tau(u)w(e)$
%        \item $ch_{\tau+1}(e^2)\oplus\beta\gamma f_\tau(v)w(e)$
%        \item $ch_{\tau+1}(v')\oplus f_\tau(v)w(e)$
%        \item $ch_{\tau+1}(v)\oplus f_\tau(u)w(e)$
%        \end{itemize}
%    \end{description}
%  \end{description}
%  \item[Case 4] $ch_\tau(u)=0$ and $ch_\tau(v)>0$.
%  Similar to Case 3.
%  \item[Final Step] Set $ch_\tau(u):=ch_\tau(v):=ch_\tau(uv):=0$
%\end{description}
%\end{algorithm}
%
killed by $v_0u_1$. (If $u_1v_1$ does not
exist or not satisfy the condition, stop extending the chain from
$v_0$ ) Repeat adding $v_1u_2, u_2v_2, ...$ this way until no new
edge is added \textit{or} adding new edge creates a loop. Finally,
extend the chain from $v'_0$ to $v'_0, u'_1, v'_1, ...$ similarly.
\end{definition}

\begin{algorithm}
\small
\caption{{\sc Move-Charge} ($e=uv$, $\tau$)} \label{alg:move_charge}%
%\begin{figure}
%\begin{tabular}{|r|}
%Use the first case that applies.
\squishlist %********************
  \item[\bf Initial] Let
    $e^1=uu'$ and $e^2=vv'$ be edges in $M_{\tau+1}$. If $e^1$ does not
    exists, let $ch_{\tau}(u)=ch_{\tau+1}(u)=0$ and $f_t(u)=0$. Do the
    same thing if $e^2$ does not exist.
    (Note that one of $e^1$ and $e^2$ must exists and must be
    $e_{\tau+1}$ as $e$ is in $M_\tau$ but not in $M_{\tau+1}$.)\\
    For any variable $v$ and value $c$, define $v\oplus c$ by
    $v:=v+c$ (i.e., increase $v$ by $c$).
  \item[\bf Case 1] When $ch_\tau(u)=ch_\tau(v)=0$ ($uv$ has no vertex
  charge and has charge at most $\alpha w(uv)$ on edge.)
    %\begin{itemize}
    \squishlist
    \item $ch_{\tau+1}(e^1)\oplus\beta\gamma f_\tau(u)w(uv)$, and, $ch_{\tau+1}(e^2)\oplus\beta\gamma f_\tau(v)w(uv)$
    \squishend
    %\end{itemize}
  %
  \item[\bf Case 2] When $ch_\tau(u)>0$ and $ch_\tau(v)>0$. ($uv$ has
  positive charge at most $\delta w(uv)$ on both vertices and charge at
  most $\beta$ on edge.)
    %\begin{itemize}
    \squishlist
    \item $ch_{\tau+1}(e^1)\oplus\beta\gamma f_\tau(u)w(uv)$, and $ch_{\tau+1}(e^2)\oplus\beta\gamma f_\tau(v)w(uv)$
    \item $ch_{\tau+1}(u)\oplus\gamma f_\tau(u)w(uv)$, and $ch_{\tau+1}(v)\oplus\gamma f_\tau(v)w(uv)$
    \squishend
    %\end{itemize}
  %
%\squishend
%\end{algorithm}
%
%\begin{algorithm}
%\scriptsize \squishlist
  \item[\bf Case 3] When $ch_\tau(u)>0$ and $ch_\tau(v)=0$. ($uv$ has
  charge only on one vertex)
  %\begin{description}
  \squishlist
  \item[\bf Case 3.1] When $ch_{\tau+1}(v)=0$ or
  $ch_\tau(v')=ch_{\tau+1}(v')=0$. (When one of $v$, $v'$ will have no charge
  at $\tau+1$. That is, $vv'$ can hold charge $\alpha$ on edge at time
  $\tau+1$.
    %\begin{itemize}
    \squishlist
    \item $ch_{\tau+1}(e^1)\oplus\beta \gamma f_\tau(u)w(e)$, and $ch_{\tau+1}(e^2)\oplus \alpha \gamma f_\tau(v)w(e)$
    \item $ch_{\tau+1}(u)\oplus f_\tau(u)w(e)$
    \squishend
    %\end{itemize}
  %
  \item[\bf Case 3.2] When $ch_{\tau+1}(v)>0$ and either $ch_\tau(v')>0$ or
  $ch_{\tau+1}(v')>0$. (That is, when $vv'$ can hold charge $\beta$
  on edge since it might receive some charge on both $v$ and $v'$.)
    %\begin{description}
    \squishlist
    \item[\bf Case 3.2.1] For $\tau'>\tau$ there is a charging chain at time $\tau'$
    (\cf\ Definition~\ref{def:charging_chain}) containing $e_2$ and $e$.
        %\begin{itemize}
        \squishlist
        \item Let $u_{k+1}, v_k, u_k, ... , v_1, u_1, v_0, v'_0, u'_1, v'_1,
         ..., u'_k, v'_k, u'_{k'+1}$, for some $k$ and $k'$  be
        such charging chain where $v_0v'_0=e_{\tau'}$
        and for all $1<i\leq k$, $u_iv_i$ = shadow-edge($v_{i-1}u_i, u_i$) and
        $u'_iv'_i$ = shadow-edge($v'_{i-1}u'_i, u'_i$).
%
        \item For any $1\leq i\leq k$, let $v_iz_i$  be an edge that kills
        $u_iv_i$. (That is, for $i$ such that $u_iv_i=e$,
        $u_{i-1}v_i=e^2$ and $v_iz_i=e^1$.) Define $v'_iz'_i$
        similarly.
%
        \item For all $1\leq i\leq k$, $ch_{\tau+1}(v_iz_i)\oplus \beta\gamma f_\tau(u_i)w(u_iv_i)$
        \item For all $1\leq i\leq k$, $ch_{\tau+1}(v_{i-1}u_i)\oplus \beta\gamma f_\tau(v_i)w(u_iv_i)$
        \item For all $0\leq i\leq k$, $ch_{\tau'}(v_i)=\gamma w(v_iu_{i+1})$
        \item For all $1\leq i\leq k$,
        $ch_{\tau}(u_iv_i)=ch_\tau(u_i)=ch_\tau(v_i)=0$.
        \squishend
        %\end{itemize}
    %
    %\textit{Note:} ***
    %
    \item[\bf Case 3.2.2] For some $\tau'>\tau$ there is \textit{no} edge
    $e_{\tau'}\in OPT$ covering $v'$
        %\begin{itemize}
        \squishlist
        \item $ch_{\tau+1}(e^1)\oplus\beta\gamma f_\tau(u)w(e)$, and $ch_{\tau+1}(e^2)\oplus\beta\gamma f_\tau(v)w(e)$
        \item $ch_{\tau+1}(v')\oplus f_\tau(v)w(e)$, and $ch_{\tau+1}(v)\oplus f_\tau(u)w(e)$
        \squishend
        %\end{itemize}
    %\end{description}
    \squishend
  %\end{description}
  \squishend
  \item[\bf Case 4] $ch_\tau(u)=0$ and $ch_\tau(v)>0$.
  Similar to Case 3.
  \item[\bf Final Step] Set $ch_\tau(u):=ch_\tau(v):=ch_\tau(uv):=0$
\squishend %
\end{algorithm}

%-------------------------------------------------------------------


Unlike other cases where charge on each edge is moved to its killers
separately, Case~3.2.1 moves charge of all edges in the charging
chain to their killers and all matching edges in the chain. As in
other cases, we move charge on each edge proportional to
$\beta\gamma$ to its both killer edges. Moreover, we put charge on
every vertex $v_i$ and $v'_i$ \textit{at time} $\tau'$.

We now ready to prove the important invariants in the next Section.
